One form of computer graphics is to develop a sequence of video image frames of an object scene from object scene information. The sources of object scene information include data stored in computer databases and data output by computer programs. The object scene information includes visual characteristics of an object scene, such as color and movement. Typically, one or more programs comprising a renderer process object scene information.
More specifically, a video image frame includes a color value for each pixel of a display device. Pixels are the smallest resolution element of the display device. A color of a given pixel is determined by processing object scene information in the general area of the pixel.
Computer graphics systems typically develop each video image frame of computer animated video by point sampling the general location of a given pixel in an object scene. Essentially, a renderer processes object scene information to calculate a color value of an object scene at an infinitesimal point within the object scene. The renderer then averages color values of a set of point samples in the general area of a pixel to compute a color for the pixel.
Other computer graphics systems reconstruct a view of an object scene by area averaging. Unlike the point sampling described above, area averaging calculates an actual view of an object scene in the general area of a pixel. The systems then compute a color value for the pixel from the view. The process is substantially more time consuming than point sampling, however, because these systems calculate a view of an entire area (instead of a set of points within the area).
Line sampling can also be used to reconstruct a view of an object scene as described in detail below.
In implementing any of the above methods to reconstruct a view of an object scene, sampling data must be maintained and updated continuously to reflect the changes in the object scene. A conventional method for data maintenance is to proceed through a linked list of ordered data sets from the beginning of the list to the end of the list. Updating data sets using this method, however, can be inefficient. For example, under the conventional method, if a data set located toward the end of the linked list requires updating, each data set located prior to the data set must be examined before the data set can be updated.
The conventional method of data maintenance requires extended processing time and consumes valuable resources when updating data sets. In addition, conventional methods for data maintenance may consume memory resources unnecessarily if extraneous sampling data is retained.
Therefore, a method of maintaining sampling data where data sets can be efficiently stored, retrieved, and updated is needed. A data storage method is required that would not consume valuable processing resources or use memory resources unnecessarily by storing extraneous sampling data.